/*
 * Created on Sep 21, 2007
 *
 * Copyright (c) 2007, the JUNG Project and the Regents of the University
 * of California
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * http://jung.sourceforge.net/license.txt for a description.
 */
package edu.uci.ics.jung.io;

import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import javax.xml.parsers.ParserConfigurationException;
import javax.xml.parsers.SAXParser;
import javax.xml.parsers.SAXParserFactory;

import org.apache.commons.collections15.BidiMap;
import org.apache.commons.collections15.Factory;
import org.apache.commons.collections15.bidimap.DualHashBidiMap;
import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;
import org.xml.sax.SAXNotSupportedException;
import org.xml.sax.helpers.DefaultHandler;

import edu.uci.ics.jung.algorithms.util.MapSettableTransformer;
import edu.uci.ics.jung.algorithms.util.SettableTransformer;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.Hypergraph;
import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;

/**
 * Reads in data from a GraphML-formatted file and generates graphs based on
 * that data.  Currently supports the following parts of the GraphML
 * specification:
 * <ul>
 * <li/>graphs and hypergraphs
 * <li/>directed and undirected edges
 * <li/>graph, vertex, edge <code>data</code>
 * <li/>graph, vertex, edge descriptions and <code>data</code> descriptions
 * <li/>vertex and edge IDs
 * </ul>
 * Each of these is exposed via appropriate <code>get</code> methods.
 *
 * Does not currently support nested graphs or ports.
 *
 * <p>Note that the user is responsible for supplying a graph
 * <code>Factory</code> that can support the edge types in the supplied
 * GraphML file.  If the graph generated by the <code>Factory</code> is
 * not compatible (for example: if the graph does not accept directed
 * edges, and the GraphML file contains a directed edge) then the results
 * are graph-implementation-dependent.
 *
 * @see "http://graphml.graphdrawing.org/specification.html"
 */
public class GraphMLReader<G extends Hypergraph<V,E>, V, E> extends DefaultHandler
{
    protected enum TagState {NO_TAG, VERTEX, EDGE, HYPEREDGE, ENDPOINT, GRAPH,
      DATA, KEY, DESC, DEFAULT_KEY, GRAPHML, OTHER}

    protected enum KeyType {NONE, VERTEX, EDGE, GRAPH, ALL}

    protected SAXParser saxp;
    protected EdgeType default_edgetype;
    protected G current_graph;
    protected V current_vertex;
    protected E current_edge;
    protected String current_key;
    protected LinkedList<TagState> current_states;
    protected BidiMap<String, TagState> tag_state;
    protected Factory<G> graph_factory;
    protected Factory<V> vertex_factory;
    protected Factory<E> edge_factory;
    protected BidiMap<V, String> vertex_ids;
    protected BidiMap<E, String> edge_ids;
    protected Map<String, GraphMLMetadata<G>> graph_metadata;
    protected Map<String, GraphMLMetadata<V>> vertex_metadata;
    protected Map<String, GraphMLMetadata<E>> edge_metadata;
    protected Map<V, String> vertex_desc;
    protected Map<E, String> edge_desc;
    protected Map<G, String> graph_desc;
    protected KeyType key_type;
    protected Collection<V> hyperedge_vertices;

    protected List<G> graphs;

    protected StringBuilder current_text = new StringBuilder();
    
    /**
     * Creates a <code>GraphMLReader</code> instance with the specified
     * vertex and edge factories.
     *
     * @param vertex_factory the vertex factory to use to create vertex objects
     * @param edge_factory the edge factory to use to create edge objects
     * @throws ParserConfigurationException
     * @throws SAXException
     */
    public GraphMLReader(Factory<V> vertex_factory,
    		Factory<E> edge_factory)
        throws ParserConfigurationException, SAXException
    {
        current_vertex = null;
        current_edge = null;

        SAXParserFactory factory = SAXParserFactory.newInstance();
        saxp = factory.newSAXParser();

        current_states = new LinkedList<TagState>();

        tag_state = new DualHashBidiMap<String, TagState>();
        tag_state.put("node", TagState.VERTEX);
        tag_state.put("edge", TagState.EDGE);
        tag_state.put("hyperedge", TagState.HYPEREDGE);
        tag_state.put("endpoint", TagState.ENDPOINT);
        tag_state.put("graph", TagState.GRAPH);
        tag_state.put("data", TagState.DATA);
        tag_state.put("key", TagState.KEY);
        tag_state.put("desc", TagState.DESC);
        tag_state.put("default", TagState.DEFAULT_KEY);
        tag_state.put("graphml", TagState.GRAPHML);

        this.key_type = KeyType.NONE;

        this.vertex_factory = vertex_factory;
        this.edge_factory = edge_factory;
    }

    /**
     * Creates a <code>GraphMLReader</code> instance that assigns the vertex
     * and edge <code>id</code> strings to be the vertex and edge objects,
     * as well as their IDs.
     * Note that this requires that (a) each edge have a valid ID, which is not
     * normally a requirement for edges in GraphML, and (b) that the vertex
     * and edge types be assignment-compatible with <code>String</code>.
     * @throws ParserConfigurationException
     * @throws SAXException
     */
    public GraphMLReader() throws ParserConfigurationException, SAXException
    {
    	this(null, null);
    }

    /**
     * Returns a list of the graphs parsed from the specified reader, as created by
     * the specified factory.
     * @throws IOException
     */
    public List<G> loadMultiple(Reader reader, Factory<G> graph_factory)
        throws IOException
    {
        this.graph_factory = graph_factory;
        initializeData();
        clearData();
        parse(reader);

        return graphs;
    }

    /**
     * Returns a list of the graphs parsed from the specified file, as created by
     * the specified factory.
     * @throws IOException
     */
    public List<G> loadMultiple(String filename, Factory<G> graph_factory) throws IOException
    {
        return loadMultiple(new FileReader(filename), graph_factory);
    }

    /**
     * Populates the specified graph with the data parsed from the reader.
     * @throws IOException
     */
    public void load(Reader reader, G g) throws IOException
    {
        this.current_graph = g;
        this.graph_factory = null;
        initializeData();
        clearData();

        parse(reader);
    }

    /**
     * Populates the specified graph with the data parsed from the specified file.
     * @throws IOException
     */
    public void load(String filename, G g) throws IOException
    {
        load(new FileReader(filename), g);
    }

    protected void clearData()
    {
        this.vertex_ids.clear();
        this.vertex_desc.clear();

        this.edge_ids.clear();
        this.edge_desc.clear();

        this.graph_desc.clear();

        this.hyperedge_vertices.clear();
    }

    /**
     * This is separate from initialize() because these data structures are shared among all
     * graphs loaded (i.e., they're defined inside <code>graphml</code> rather than <code>graph</code>.
     */
    protected void initializeData()
    {
        this.vertex_ids = new DualHashBidiMap<V, String>();
        this.vertex_desc = new HashMap<V, String>();
        this.vertex_metadata = new HashMap<String, GraphMLMetadata<V>>();

        this.edge_ids = new DualHashBidiMap<E, String>();
        this.edge_desc = new HashMap<E, String>();
        this.edge_metadata = new HashMap<String, GraphMLMetadata<E>>();

        this.graph_desc = new HashMap<G, String>();
        this.graph_metadata = new HashMap<String, GraphMLMetadata<G>>();

        this.hyperedge_vertices = new ArrayList<V>();
    }

    protected void parse(Reader reader) throws IOException
    {
        try
        {
            saxp.parse(new InputSource(reader), this);
            reader.close();
        }
        catch (SAXException saxe)
        {
            throw new IOException(saxe.getMessage());
        }
    }

    @Override
    public void startElement(String uri, String name, String qName, Attributes atts) throws SAXNotSupportedException
    {
        String tag = qName.toLowerCase();
        TagState state = tag_state.get(tag);
        if (state == null)
            state = TagState.OTHER;

        switch (state)
        {
            case GRAPHML:
                break;

            case VERTEX:
                if (this.current_graph == null)
                    throw new SAXNotSupportedException("Graph must be defined prior to elements");
                if (this.current_edge != null || this.current_vertex != null)
                    throw new SAXNotSupportedException("Nesting elements not supported");

                createVertex(atts);

                break;

            case ENDPOINT:
                if (this.current_graph == null)
                    throw new SAXNotSupportedException("Graph must be defined prior to elements");
                if (this.current_edge == null)
                    throw new SAXNotSupportedException("No edge defined for endpoint");
                if (this.current_states.getFirst() != TagState.HYPEREDGE)
                    throw new SAXNotSupportedException("Endpoints must be defined inside hyperedge");
                Map<String, String> endpoint_atts = getAttributeMap(atts);
                String node = endpoint_atts.remove("node");
                if (node == null)
                    throw new SAXNotSupportedException("Endpoint must include an 'id' attribute");
                V v = vertex_ids.getKey(node);
                if (v == null)
                    throw new SAXNotSupportedException("Endpoint refers to nonexistent node ID: " + node);

                this.current_vertex = v;
                hyperedge_vertices.add(v);
                break;

            case EDGE:
            case HYPEREDGE:
                if (this.current_graph == null)
                    throw new SAXNotSupportedException("Graph must be defined prior to elements");
                if (this.current_edge != null || this.current_vertex != null)
                    throw new SAXNotSupportedException("Nesting elements not supported");

                createEdge(atts, state);
                break;

            case GRAPH:
                if (this.current_graph != null && graph_factory != null)
                    throw new SAXNotSupportedException("Nesting graphs not currently supported");

                // graph factory is null if there's only one graph
                if (graph_factory != null)
                    current_graph = graph_factory.create();

                // reset all non-key data structures (to avoid collisions between different graphs)
                clearData();

                // set up default direction of edges
                Map<String, String> graph_atts = getAttributeMap(atts);
                String default_direction = graph_atts.remove("edgedefault");
                if (default_direction == null)
                    throw new SAXNotSupportedException("All graphs must specify a default edge direction");
                if (default_direction.equals("directed"))
                    this.default_edgetype = EdgeType.DIRECTED;
                else if (default_direction.equals("undirected"))
                    this.default_edgetype = EdgeType.UNDIRECTED;
                else
                    throw new SAXNotSupportedException("Invalid or unrecognized default edge direction: " + default_direction);

                // put remaining attribute/value pairs in graph_data
            	addExtraData(graph_atts, graph_metadata, current_graph);

                break;

            case DATA:
                if (this.current_states.contains(TagState.DATA))
                    throw new SAXNotSupportedException("Nested data not supported");
                handleData(atts);
                break;

            case KEY:
                createKey(atts);
                break;


            default:
                break;
        }

        current_states.addFirst(state);
    }

    /**
     *
     * @param <T>
     * @param atts
     * @param metadata_map
     * @param current_elt
     */
	protected <T>void addExtraData(Map<String, String> atts,
			Map<String, GraphMLMetadata<T>> metadata_map, T current_elt)
	{
		// load in the default values; these override anything that might
		// be in the attribute map (because that's not really a proper
		// way to associate data)
        for (Map.Entry<String, GraphMLMetadata<T>> entry: metadata_map.entrySet())
        {
        	GraphMLMetadata<T> gmlm = entry.getValue();
        	if (gmlm.default_value != null)
        	{
            	SettableTransformer<T, String> st =
            		(SettableTransformer<T, String>)gmlm.transformer;
        		st.set(current_elt, gmlm.default_value);
        	}
        }

        // place remaining items in data
        for (Map.Entry<String, String> entry : atts.entrySet())
        {
			String key = entry.getKey();
			GraphMLMetadata<T> key_data = metadata_map.get(key);
			SettableTransformer<T, String> st;
			if (key_data != null)
			{
				// if there's a default value, don't override it
				if (key_data.default_value != null)
					continue;
				st = (SettableTransformer<T, String>)key_data.transformer;
			}
			else
			{
				st = new MapSettableTransformer<T, String>(
							new HashMap<T, String>());
				key_data = new GraphMLMetadata<T>(null, null, st);
				metadata_map.put(key, key_data);
			}
			st.set(current_elt, entry.getValue());
        }
	}


    @Override
    public void characters(char[] ch, int start, int length) throws SAXNotSupportedException
    {
        this.current_text.append(new String(ch, start, length));
    }


    protected <T>void addDatum(Map<String, GraphMLMetadata<T>> metadata,
    		T current_elt, String text) throws SAXNotSupportedException
    {
        if (metadata.containsKey(this.current_key))
        {
        	SettableTransformer<T, String> st =
        		(SettableTransformer<T, String>)(metadata.get(this.current_key).transformer);
            st.set(current_elt, text);
        }
        else
            throw new SAXNotSupportedException("key " + this.current_key +
            		" not valid for element " + current_elt);
    }

    @Override
    public void endElement(String uri, String name, String qName) throws SAXNotSupportedException
    {
        String text = current_text.toString().trim();
        current_text.setLength(0);
        
        String tag = qName.toLowerCase();
        TagState state = tag_state.get(tag);
        if (state == null)
            state = TagState.OTHER;
        if (state == TagState.OTHER)
            return;

        if (state != current_states.getFirst())
            throw new SAXNotSupportedException("Unbalanced tags: opened " +
            		tag_state.getKey(current_states.getFirst()) +
                    ", closed " + tag);

        switch(state)
        {
            case VERTEX:
            case ENDPOINT:
                current_vertex = null;
                break;

            case EDGE:
                current_edge = null;
                break;

            case HYPEREDGE:
                current_graph.addEdge(current_edge, hyperedge_vertices);
                hyperedge_vertices.clear();
                current_edge = null;
                break;

            case GRAPH:
                current_graph = null;
                break;

            case KEY:
                current_key = null;
                break;

            case DESC:
                switch (this.current_states.get(1)) // go back one
                {
                    case GRAPH:
                        graph_desc.put(current_graph, text);
                        break;
                    case VERTEX:
                    case ENDPOINT:
                        vertex_desc.put(current_vertex, text);
                        break;
                    case EDGE:
                    case HYPEREDGE:
                        edge_desc.put(current_edge, text);
                        break;
                    case DATA:
                        switch (key_type)
                        {
                            case GRAPH:
                                graph_metadata.get(current_key).description = text;
                                break;
                            case VERTEX:
                                vertex_metadata.get(current_key).description = text;
                                break;
                            case EDGE:
                                edge_metadata.get(current_key).description = text;
                                break;
                            case ALL:
                                graph_metadata.get(current_key).description = text;
                                vertex_metadata.get(current_key).description = text;
                                edge_metadata.get(current_key).description = text;
                                break;
                            default:
                                throw new SAXNotSupportedException("Invalid key type" +
                                        " specified for default: " + key_type);
                        }

                        break;
                    default:
                        break;
                }
                break;
            case DATA:
                this.key_type = KeyType.NONE;
                switch (this.current_states.get(1))
                {
                    case GRAPH:
                        addDatum(graph_metadata, current_graph, text);
                        break;
                    case VERTEX:
                    case ENDPOINT:
                        addDatum(vertex_metadata, current_vertex, text);
                        break;
                    case EDGE:
                    case HYPEREDGE:
                        addDatum(edge_metadata, current_edge, text);
                        break;
                    default:
                        break;
                }
                break;
            case DEFAULT_KEY:
                if (this.current_states.get(1) != TagState.KEY)
                    throw new SAXNotSupportedException("'default' only defined in context of 'key' tag: " +
                            "stack: " + current_states.toString());

                switch (key_type)
                {
                    case GRAPH:
                        graph_metadata.get(current_key).default_value = text;
                        break;
                    case VERTEX:
                        vertex_metadata.get(current_key).default_value = text;
                        break;
                    case EDGE:
                        edge_metadata.get(current_key).default_value = text;
                        break;
                    case ALL:
                        graph_metadata.get(current_key).default_value = text;
                        vertex_metadata.get(current_key).default_value = text;
                        edge_metadata.get(current_key).default_value = text;
                        break;
                    default:
                        throw new SAXNotSupportedException("Invalid key type" +
                                " specified for default: " + key_type);
                }

                break;
            default:
                break;
        }

        current_states.removeFirst();
    }

    protected Map<String, String> getAttributeMap(Attributes atts)
    {
        Map<String,String> att_map = new HashMap<String,String>();
        for (int i = 0; i < atts.getLength(); i++)
            att_map.put(atts.getQName(i), atts.getValue(i));

        return att_map;
    }

    protected void handleData(Attributes atts) throws SAXNotSupportedException
    {
        switch (this.current_states.getFirst())
        {
            case GRAPH:
                break;
            case VERTEX:
            case ENDPOINT:
                break;
            case EDGE:
                break;
            case HYPEREDGE:
                break;
            default:
                throw new SAXNotSupportedException("'data' tag only defined " +
                		"if immediately containing tag is 'graph', 'node', " +
                        "'edge', or 'hyperedge'");
        }
        this.current_key = getAttributeMap(atts).get("key");
        if (this.current_key == null)
            throw new SAXNotSupportedException("'data' tag requires a key specification");
        if (this.current_key.equals(""))
            throw new SAXNotSupportedException("'data' tag requires a non-empty key");
        if (!getGraphMetadata().containsKey(this.current_key) &&
            !getVertexMetadata().containsKey(this.current_key) &&
            !getEdgeMetadata().containsKey(this.current_key))
        {
            throw new SAXNotSupportedException("'data' tag's key specification must reference a defined key");
        }

    }

    protected void createKey(Attributes atts) throws SAXNotSupportedException
    {
        Map<String, String> key_atts = getAttributeMap(atts);
        String id = key_atts.remove("id");
        String for_type = key_atts.remove("for");

        if (for_type == null || for_type.equals("") || for_type.equals("all"))
        {
            vertex_metadata.put(id,
            		new GraphMLMetadata<V>(null, null,
            				new MapSettableTransformer<V, String>(new HashMap<V, String>())));
            edge_metadata.put(id,
            		new GraphMLMetadata<E>(null, null,
            				new MapSettableTransformer<E, String>(new HashMap<E, String>())));
            graph_metadata.put(id,
            		new GraphMLMetadata<G>(null, null,
            				new MapSettableTransformer<G, String>(new HashMap<G, String>())));
            key_type = KeyType.ALL;
        }
        else
        {
            TagState type = tag_state.get(for_type);
            switch (type)
            {
                case VERTEX:
                    vertex_metadata.put(id,
                    		new GraphMLMetadata<V>(null, null,
                    				new MapSettableTransformer<V, String>(new HashMap<V, String>())));
                    key_type = KeyType.VERTEX;
                    break;
                case EDGE:
                case HYPEREDGE:
                    edge_metadata.put(id,
                    		new GraphMLMetadata<E>(null, null,
                    				new MapSettableTransformer<E, String>(new HashMap<E, String>())));
                    key_type = KeyType.EDGE;
                    break;
                case GRAPH:
                    graph_metadata.put(id,
                    		new GraphMLMetadata<G>(null, null,
                    				new MapSettableTransformer<G, String>(new HashMap<G, String>())));
                    key_type = KeyType.GRAPH;
                    break;
                default:
                	throw new SAXNotSupportedException(
                			"Invalid metadata target type: " + for_type);
            }
        }

        this.current_key = id;

    }

    @SuppressWarnings("unchecked")
	protected void createVertex(Attributes atts) throws SAXNotSupportedException
    {
        Map<String, String> vertex_atts = getAttributeMap(atts);
        String id = vertex_atts.remove("id");
        if (id == null)
            throw new SAXNotSupportedException("node attribute list missing " +
            		"'id': " + atts.toString());
        V v = vertex_ids.getKey(id);

        if (v == null)
        {
        	if (vertex_factory != null)
        		v = vertex_factory.create();
        	else
        		v = (V)id;
            vertex_ids.put(v, id);
            this.current_graph.addVertex(v);

            // put remaining attribute/value pairs in vertex_data
           	addExtraData(vertex_atts, vertex_metadata, v);
        }
        else
            throw new SAXNotSupportedException("Node id \"" + id +
            		" is a duplicate of an existing node ID");

        this.current_vertex = v;
    }


    @SuppressWarnings("unchecked")
	protected void createEdge(Attributes atts, TagState state)
    	throws SAXNotSupportedException
    {
        Map<String,String> edge_atts = getAttributeMap(atts);

        String id = edge_atts.remove("id");
        E e;
        if (edge_factory != null)
        	e = edge_factory.create();
        else
            if (id != null)
                e = (E)id;
            else
                throw new IllegalArgumentException("If no edge factory is supplied, " +
                		"edge id may not be null: " + edge_atts);

        if (id != null)
        {
            if (edge_ids.containsKey(e))
                throw new SAXNotSupportedException("Edge id \"" + id +
                		"\" is a duplicate of an existing edge ID");
            edge_ids.put(e, id);
        }

        if (state == TagState.EDGE)
        	assignEdgeSourceTarget(e, atts, edge_atts); //, id);

        // put remaining attribute/value pairs in edge_data
        addExtraData(edge_atts, edge_metadata, e);

        this.current_edge = e;
    }

    protected void assignEdgeSourceTarget(E e, Attributes atts,
    		Map<String, String> edge_atts)//, String id)
    	throws SAXNotSupportedException
    {
        String source_id = edge_atts.remove("source");
        if (source_id == null)
            throw new SAXNotSupportedException("edge attribute list missing " +
            		"'source': " + atts.toString());
        V source = vertex_ids.getKey(source_id);
        if (source == null)
            throw new SAXNotSupportedException("specified 'source' attribute " +
            		"\"" + source_id + "\" does not match any node ID");

        String target_id = edge_atts.remove("target");
        if (target_id == null)
            throw new SAXNotSupportedException("edge attribute list missing " +
            		"'target': " + atts.toString());
        V target = vertex_ids.getKey(target_id);
        if (target == null)
            throw new SAXNotSupportedException("specified 'target' attribute " +
            		"\"" + target_id + "\" does not match any node ID");

        String directed = edge_atts.remove("directed");
        EdgeType edge_type;
        if (directed == null)
            edge_type = default_edgetype;
        else if (directed.equals("true"))
            edge_type = EdgeType.DIRECTED;
        else if (directed.equals("false"))
            edge_type = EdgeType.UNDIRECTED;
        else
            throw new SAXNotSupportedException("Unrecognized edge direction specifier 'direction=\"" +
            		directed + "\"': " + "source: " + source_id + ", target: " + target_id);

        if (current_graph instanceof Graph)
            ((Graph<V,E>)this.current_graph).addEdge(e, source, target,
            		edge_type);
        else
            this.current_graph.addEdge(e, new Pair<V>(source, target));
    }

    /**
     * Returns a bidirectional map relating vertices and IDs.
     */
    public BidiMap<V, String> getVertexIDs()
    {
        return vertex_ids;
    }

    /**
     * Returns a bidirectional map relating edges and IDs.
     * This is not guaranteed to always be populated (edge IDs are not
     * required in GraphML files.
     */
    public BidiMap<E, String> getEdgeIDs()
    {
        return edge_ids;
    }

    /**
     * Returns a map from graph type name to type metadata.
     */
    public Map<String, GraphMLMetadata<G>> getGraphMetadata()
    {
    	return graph_metadata;
    }

    /**
     * Returns a map from vertex type name to type metadata.
     */
    public Map<String, GraphMLMetadata<V>> getVertexMetadata()
    {
    	return vertex_metadata;
    }

    /**
     * Returns a map from edge type name to type metadata.
     */
    public Map<String, GraphMLMetadata<E>> getEdgeMetadata()
    {
    	return edge_metadata;
    }

    /**
     * Returns a map from graphs to graph descriptions.
     */
    public Map<G, String> getGraphDescriptions()
    {
        return graph_desc;
    }

    /**
     * Returns a map from vertices to vertex descriptions.
     */
    public Map<V, String> getVertexDescriptions()
    {
        return vertex_desc;
    }

    /**
     * Returns a map from edges to edge descriptions.
     */
    public Map<E, String> getEdgeDescriptions()
    {
        return edge_desc;
    }
}
